{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #验证二叉搜索树的后序遍历序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #binary-search-tree #recursion #binary-tree #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #二叉搜索树 #递归 #二叉树 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: verifyTreeOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证二叉搜索树的后序遍历序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请实现一个函数来判断整数数组 <code>postorder</code> 是否为二叉搜索树的后序遍历结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694762751-fwHhWX-%E5%89%91%E6%8C%8733%E7%A4%BA%E4%BE%8B1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>postorder = [4,9,6,9,8]\n",
    "<strong>输出: </strong>false \n",
    "<strong>解释：</strong>从上图可以看出这不是一颗二叉搜索树\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694762510-vVpTic-%E5%89%91%E6%8C%8733.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>postorder = [4,6,5,9,8]\n",
    "<strong>输出: </strong>true \n",
    "<strong>解释：</strong>可构建的二叉搜索树如上图\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>数组长度 &lt;= 1000</code></li>\n",
    "\t<li><code>postorder</code> 中无重复数字</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,9,6,5,8]', '[4,6,5,9,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def fun(nums, minV, maxV):\n",
    "            if not nums:\n",
    "                return \n",
    "            tmp = nums[-1]\n",
    "            if not minV < tmp < maxV:\n",
    "                return \n",
    "            nums.pop()\n",
    "            fun(nums, tmp, maxV)\n",
    "            fun(nums, minV, tmp)\n",
    "\n",
    "            \n",
    "            \n",
    "        fun(postorder, -sys.maxsize, sys.maxsize)\n",
    "        return not postorder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j: return True\n",
    "            p = i\n",
    "            while postorder[p] < postorder[j]: p += 1\n",
    "            m = p\n",
    "            while postorder[p] > postorder[j]: p += 1\n",
    "            return p == j and recur(i, m - 1) and recur(m, j - 1)\n",
    "\n",
    "        return recur(0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j: return True\n",
    "            p = i\n",
    "            while postorder[p] < postorder[j]: p += 1\n",
    "            m = p\n",
    "            while postorder[p] > postorder[j]: p += 1\n",
    "            return p == j and recur(i, m - 1) and recur(m, j - 1)\n",
    "        return recur(0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            p = i\n",
    "            while postorder[p] < postorder[j]:\n",
    "                p += 1\n",
    "            m = p\n",
    "            while postorder[p] > postorder[j]:\n",
    "                p += 1\n",
    "            return p == j and recur(i, m - 1) and recur(m, j - 1)\n",
    "        return recur(0, len(postorder) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if not postorder:\n",
    "            return True\n",
    "\n",
    "        def dfs(left,right):\n",
    "            if left>=right: return True\n",
    "            rr = postorder[right]\n",
    "            p = left\n",
    "            while p<right:\n",
    "                if postorder[p]<rr:\n",
    "                    p+=1\n",
    "                else:\n",
    "                    break\n",
    "            lr = p-1\n",
    "            while p <right:\n",
    "                if postorder[p]>rr:\n",
    "                    p+=1\n",
    "                else:\n",
    "                    break\n",
    "            if p != right:\n",
    "                return False\n",
    "            return dfs(left,lr)and dfs(lr+1,right-1)\n",
    "        return dfs(0,len(postorder)-1)\n",
    "            \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "#\n",
    "# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可\n",
    "#\n",
    "#\n",
    "# @param sequence int整型一维数组\n",
    "# @return bool布尔型\n",
    "#\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self , sequence) :\n",
    "        # write code here\n",
    "        if not sequence:\n",
    "            return True\n",
    "\n",
    "        root = sequence[-1]\n",
    "\n",
    "        left = True\n",
    "        right = True\n",
    "\n",
    "        i = 0\n",
    "        while sequence[i]<root:\n",
    "            i = i+1\n",
    "\n",
    "        j = i\n",
    "        while j<len(sequence)-1:\n",
    "            if sequence[j]<root:\n",
    "                return False\n",
    "            j = j + 1\n",
    "        if i> 0:\n",
    "            left = self.verifyTreeOrder(sequence[0:i])\n",
    "        if i < len(sequence)-1:\n",
    "            right = self.verifyTreeOrder(sequence[i:len(sequence)-1])\n",
    "\n",
    "        return left and right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        i = 0 \n",
    "        j = len(postorder) - 1\n",
    "        def isTrue(i, j, l, r):\n",
    "            if i >= j:\n",
    "                return True\n",
    "\n",
    "            if postorder[j] < l or postorder[j] > r:\n",
    "                return False\n",
    "\n",
    "\n",
    "            for k in range(i, j+1):\n",
    "                if postorder[k] >= postorder[j]:\n",
    "                    break\n",
    "\n",
    "            p1 = isTrue(i, k-1, l, postorder[j])\n",
    "            p2 = isTrue(k, j-1, postorder[j], r)\n",
    "            return p1 and p2\n",
    "\n",
    "        return isTrue(0, j, -inf, inf)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, postorder, i, j):\n",
    "        if i >= j:\n",
    "            return True\n",
    "        root = postorder[j]\n",
    "        left = i\n",
    "        while left < j and postorder[left] < root:\n",
    "            left += 1\n",
    "        right = left\n",
    "        while right < j and postorder[right] > root:\n",
    "            right += 1\n",
    "        if right != j:\n",
    "            return False\n",
    "        return self.check(postorder, i, left - 1) and self.check(postorder, left, j - 1)\n",
    "        \n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        return self.check(postorder, 0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if not postorder: \n",
    "            return True\n",
    "        # 递归进行\n",
    "        root = postorder[-1]\n",
    "        indexLeft = 0\n",
    "        while indexLeft != len(postorder) - 1: \n",
    "            if postorder[indexLeft] >= root: break\n",
    "            indexLeft += 1\n",
    "        indexRight = indexLeft\n",
    "        while indexRight != len(postorder) - 1: \n",
    "            if postorder[indexRight] < root: \n",
    "                return False\n",
    "            indexRight += 1\n",
    "\n",
    "        left, right = True, True\n",
    "        if indexLeft > 0: \n",
    "            left = self.verifyTreeOrder(postorder[0:indexLeft])\n",
    "        if indexLeft < len(postorder) - 1: \n",
    "            right = self.verifyTreeOrder(postorder[indexLeft:-1])\n",
    "        return left and right\n",
    "        \n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        # def verify(order: List[int], left: int, right: int) -> bool:\n",
    "        #     if left >= right:\n",
    "        #         return True\n",
    "        #     mid = left\n",
    "        #     root = order[right]\n",
    "        #     while order[mid] < root:\n",
    "        #         mid += 1\n",
    "        #     temp = mid\n",
    "        #     while temp < right:\n",
    "        #         if order[temp] < root:\n",
    "        #             return False\n",
    "        #     return verify(order, left, mid - 1) and verify(order, mid, right)\n",
    "        \n",
    "        # return verify(postorder, 0, len(postorder) - 1)\n",
    "        if postorder is None:\n",
    "            return False\n",
    "        if len(postorder) <= 2:\n",
    "            return True\n",
    "        right = -1\n",
    "        flag = False\n",
    "        for index, val in enumerate(postorder):\n",
    "            if val > postorder[-1] and not flag:\n",
    "                right = index\n",
    "                flag = True\n",
    "            elif val < postorder[-1] and flag:\n",
    "                return False\n",
    "        if right == 0:\n",
    "            return self.verifyTreeOrder(postorder[:-1])\n",
    "        elif right == -1:\n",
    "            return self.verifyTreeOrder(postorder[:-1])\n",
    "        else:\n",
    "            return self.verifyTreeOrder(postorder[:right]) and self.verifyTreeOrder(postorder[right:-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        stack, root = [], float(\"+inf\")\n",
    "        for i in range(len(postorder)-1,-1,-1):\n",
    "            if postorder[i]>root:return False\n",
    "            while (stack and postorder[i]<stack[-1]):\n",
    "                root = stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        return self.check(postorder, 0, len(postorder) - 1)\n",
    "    \n",
    "    def check(self, postorder, i, j):\n",
    "        # 说明此子树节点数量 <= 1, 无需判别正确性, 因此直接返回 true\n",
    "        if i >= j:\n",
    "            return True\n",
    "        \n",
    "        # 根节点的值是后序遍历结果的最后一个元素\n",
    "        root = postorder[j]\n",
    "\n",
    "        # postorder[i..left) 是左子树，应该都小于 root\n",
    "        left = i\n",
    "        while left < j and postorder[left] < root:\n",
    "            left += 1\n",
    "        \n",
    "        # postorder[left..j) 是右子树，应该都大于 root\n",
    "        right = left\n",
    "        while right < j and postorder[right] > root:\n",
    "            right += 1\n",
    "        \n",
    "        if right != j:\n",
    "            return False\n",
    "        # 递归检查左子树 [i..left) 和右子树 [left..j) 也符合二叉搜索树的性质\n",
    "        return self.check(postorder, i, left - 1) and self.check(postorder, left, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def dfs(first, end):\n",
    "            # 终止条件\n",
    "            if first>= end: return True\n",
    "            position = first\n",
    "            while postorder[position] < postorder[end]: position+=1\n",
    "            # 需要一个变量记录左子树的区间范围，在后序遍历中\n",
    "            m = position\n",
    "            while postorder[position] > postorder[end]: position+=1\n",
    "            # 当position==end 说明已经找到了右子树的区间范围\n",
    "            return position==end and dfs(first, m-1) and dfs(m,position-1)\n",
    "        \n",
    "        return dfs(0, len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if len(postorder) <= 1:\n",
    "            return True\n",
    "        t = 0\n",
    "        for i in range(len(postorder)-1):\n",
    "            if postorder[i] < postorder[-1]:\n",
    "                t = i+1\n",
    "            else:\n",
    "                break\n",
    "        # print(postorder, t)\n",
    "        for i in range(t,len(postorder)-1):\n",
    "            if postorder[i] <= postorder[-1]:\n",
    "                return False\n",
    "        return self.verifyTreeOrder(postorder[:t]) and self.verifyTreeOrder(postorder[t:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        stack, root = [], float(\"+inf\")\n",
    "        for i in range(len(postorder) - 1, -1, -1):\n",
    "            if postorder[i] > root: return False\n",
    "            while(stack and postorder[i] < stack[-1]):\n",
    "                root = stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        stack, root = [], float(\"+inf\")\n",
    "        for i in range(len(postorder) - 1, -1, -1):\n",
    "            if postorder[i] > root: return False\n",
    "            while(stack and postorder[i] < stack[-1]):\n",
    "                root = stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def fun(nums, minV, maxV):\n",
    "            if not nums:\n",
    "                return True \n",
    "            tmp = nums[-1]\n",
    "            if not minV < tmp < maxV:\n",
    "                return False \n",
    "            nums.pop()\n",
    "            fun(nums, tmp, maxV)\n",
    "            fun(nums, minV, tmp)\n",
    "        fun(postorder, -sys.maxsize, sys.maxsize)    \n",
    "        return not postorder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if len(postorder)<=1:\n",
    "            return True\n",
    "        n=len(postorder)\n",
    "        judge=False\n",
    "        rstart=None\n",
    "        left=True\n",
    "        right=True\n",
    "        for i in range(n-1):\n",
    "            if postorder[i]>postorder[-1] and judge==False:\n",
    "                rstart=i\n",
    "                judge=True\n",
    "            if rstart!=None and i>rstart and judge:\n",
    "                \n",
    "                if postorder[i]<=postorder[-1]:\n",
    "                    return False \n",
    "        if rstart==None:\n",
    "            left=True\n",
    "        else:\n",
    "            left=self.verifyTreeOrder(postorder[:rstart])\n",
    "        \n",
    "        right=self.verifyTreeOrder(postorder[rstart:n-1])\n",
    "        return left and right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i,j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            root = postorder[j]\n",
    "            tmp = i\n",
    "            while postorder[tmp] < root:\n",
    "                tmp += 1\n",
    "            m = tmp\n",
    "            while postorder[tmp] > root:\n",
    "                tmp += 1\n",
    "            return tmp == j and recur(i,m-1) and recur(m,j-1)\n",
    "\n",
    "        return recur(0,len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "\n",
    "\n",
    "        def helper(left, right):\n",
    "            if left >= right:\n",
    "                return True\n",
    "            root_val = postorder[right]\n",
    "            p = left\n",
    "            while postorder[p] < root_val:\n",
    "                p += 1\n",
    "            mid = p\n",
    "            while postorder[p] > root_val:\n",
    "                p += 1\n",
    "            return p == right and helper(left, mid - 1) and helper(mid, right - 1)\n",
    "\n",
    "        return helper(0, len(postorder) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if not postorder:\n",
    "            return True\n",
    "        root = postorder[-1]\n",
    "        index = -1\n",
    "        for i in range(len(postorder)-1):\n",
    "            if postorder[i] > root and index == -1:\n",
    "                index = i\n",
    "            if index != -1 and postorder[i] < root:\n",
    "                return False\n",
    "        # print(postorder[:index], postorder[index+1:-1])\n",
    "        return self.verifyTreeOrder(postorder[:index]) and self.verifyTreeOrder(postorder[index:-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        stack = []\n",
    "        root = float(\"+inf\")\n",
    "        for i in range(len(postorder) - 1, -1, -1):\n",
    "            if postorder[i] > root:\n",
    "                return False\n",
    "            while (stack and postorder[i] < stack[-1]):\n",
    "                root = stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        root = 2147483647\n",
    "        s = []\n",
    "        for i in range(len(postorder) - 1, -1, -1):\n",
    "            # 到这里的根节点就是最下面的右子树了，如果左边节点有超过这个的话就错了\n",
    "            if postorder[i] > root:\n",
    "                return False\n",
    "            else:\n",
    "                # 当s有数且当前值小于栈顶元素，则是左节点了\n",
    "                while s and s[-1] > postorder[i]:\n",
    "                    # 弹出，知道栈顶小于当且数\n",
    "                    root = s.pop()\n",
    "                # 将当前元素压栈，看看他有没有右节点\n",
    "                s.append(postorder[i])\n",
    "        return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if len(postorder) <= 2:\n",
    "            return True\n",
    "        return self.delect(postorder)\n",
    "    \n",
    "    def delect(self, postorder):\n",
    "        if len(postorder) <= 1:\n",
    "            return True\n",
    "        root = postorder[-1]\n",
    "        for i in range(len(postorder)):\n",
    "            if postorder[i] > root:\n",
    "                break\n",
    "        if i == len(postorder) -1: # 没有右子树\n",
    "            return self.delect(postorder[:-1])\n",
    "        else:\n",
    "            for j in range(i, len(postorder)):\n",
    "                if postorder[j] < root:\n",
    "                    return False\n",
    "            if i == 0: # 没有左子树\n",
    "                return self.delect(postorder[0:-1])\n",
    "            else:\n",
    "                return self.delect(postorder[0:i]) and self.delect(postorder[i:-1])\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def verify(i, j):\n",
    "            if i >= j: return True\n",
    "            index = i\n",
    "            while postorder[index] < postorder[j]: index += 1\n",
    "\n",
    "            right = index\n",
    "            while postorder[index] > postorder[j]: index += 1\n",
    "\n",
    "            return index == j and verify(i, right-1) and verify(right, j-1)\n",
    "        \n",
    "        return verify(0, len(postorder)-1)\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        stack, root = [], float(\"+inf\")\n",
    "        for i in range(len(postorder) - 1, -1, -1):\n",
    "            if postorder[i] > root: return False\n",
    "            while(stack and postorder[i] < stack[-1]):\n",
    "                root = stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i,j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            root = postorder[j]\n",
    "            tmp = i\n",
    "            while postorder[tmp] < root:\n",
    "                tmp += 1\n",
    "            m = tmp\n",
    "            while postorder[tmp] > root:\n",
    "                tmp += 1\n",
    "            if  tmp == j:\n",
    "                return recur(i,m-1) and recur(m,j-1)\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return recur(0,len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            p = i\n",
    "            while postorder[p] < postorder[j]:\n",
    "                p += 1\n",
    "            m = p\n",
    "            while postorder[p] > postorder[j]:\n",
    "                p += 1\n",
    "            return p == j and recur(i, m - 1) and recur(m, j - 1)\n",
    "        \n",
    "        return recur(0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        i = 0 \n",
    "        j = len(postorder) - 1\n",
    "        def isTrue(i, j, l, r):\n",
    "            if i > j:\n",
    "                return True\n",
    "\n",
    "            if postorder[j] < l or postorder[j] > r:\n",
    "                return False\n",
    "\n",
    "            if i == j:\n",
    "                return True    \n",
    "\n",
    "            for k in range(i, j+1):\n",
    "                if postorder[k] >= postorder[j]:\n",
    "                    break\n",
    "\n",
    "            p1 = isTrue(i, k-1, l, postorder[j])\n",
    "            p2 = isTrue(k, j-1, postorder[j], r)\n",
    "            return p1 and p2\n",
    "\n",
    "        return isTrue(0, j, -inf, inf)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        lens=len(postorder)\n",
    "        if lens<=1:\n",
    "            return True\n",
    "        minpo,maxpo=lens-1,lens-2\n",
    "        if postorder[maxpo]<postorder[-1]:\n",
    "            minpo=maxpo\n",
    "        else:\n",
    "            for i in range(lens-2,-1,-1):\n",
    "                if postorder[minpo]>postorder[i]:\n",
    "                    minpo=i\n",
    "                    break\n",
    "                else:\n",
    "                    minpo=-1\n",
    "        for i in range(minpo):\n",
    "            if postorder[i]>postorder[-1]:\n",
    "                return False\n",
    "        for j in range(minpo+1,maxpo):\n",
    "            if postorder[j]<postorder[-1]:\n",
    "                return False\n",
    "        return  self.verifyTreeOrder(postorder[0:minpo+1]) and self.verifyTreeOrder(postorder[minpo+1:maxpo+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def fenge(i,j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            right=i\n",
    "            while postorder[right]<postorder[j]:\n",
    "                right=right+1\n",
    "            redex=right\n",
    "            while postorder[right]>postorder[j]:\n",
    "                right=right+1\n",
    "            return right==j and fenge(i,redex-1) and fenge(redex,j-1)\n",
    "        return fenge(0,len(postorder)-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        # 后序遍历：左右根\n",
    "        stack=[]\n",
    "        root=float(\"inf\")\n",
    "        # 后序遍历倒序：根右左\n",
    "        for i in range(len(postorder)-1,-1,-1):\n",
    "            if postorder[i]>root:\n",
    "                return False\n",
    "            # 单调递增栈\n",
    "            while stack and postorder[i]<stack[-1]:\n",
    "                root=stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        n = len(postorder)\n",
    "        # print(\"n\", n)\n",
    "        if n == 0 or n == 1 or n == 2: return True\n",
    "        root = postorder[-1]\n",
    "        k = n - 1\n",
    "        for i in range(n - 1):\n",
    "            if postorder[i] > root:\n",
    "                k = i\n",
    "                break\n",
    "        # print(\"k\", k)\n",
    "        if k != n - 1:\n",
    "            for j in range(k, n - 1):\n",
    "                if postorder[j] < root:\n",
    "                    return False      \n",
    "        if k == 0:        # 只有右子树\n",
    "            return self.verifyTreeOrder(postorder[: n - 1])\n",
    "        elif k == n - 1:\n",
    "            return self.verifyTreeOrder(postorder[:  n - 1])\n",
    "        else:\n",
    "            return self.verifyTreeOrder(postorder[:  k]) and self.verifyTreeOrder(postorder[k : n - 1])       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if not postorder:\n",
    "            return True\n",
    "        return self.digui(postorder)\n",
    "    def digui(self, postorder):\n",
    "        if not postorder:\n",
    "            return True\n",
    "        elif len(postorder) == 1:\n",
    "            return True\n",
    "        rootval = postorder[-1]\n",
    "        leftindex = 0\n",
    "        for i in range(len(postorder)):\n",
    "            if postorder[i] >= rootval:\n",
    "                leftindex = i - 1\n",
    "                break\n",
    "        for i in range(leftindex + 1, len(postorder)):\n",
    "            if postorder[i] < rootval:\n",
    "                return False\n",
    "        return self.digui(postorder[:leftindex + 1]) and self.digui(postorder[leftindex + 1: len(postorder) - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        return self.func(postorder, 0, len(postorder)-1)\n",
    "\n",
    "    # 后序遍历：左、右、中\n",
    "    def func(self, arr, si, ei):\n",
    "        # 若当前子树为空则返回True\n",
    "        if si >= ei: return True\n",
    "        meet_the_most_left = False\n",
    "        next_root = si\n",
    "        for i in range(ei-1, si-1, -1):\n",
    "            # 先扫描最左侧的左子树\n",
    "            if not meet_the_most_left and arr[i] < arr[ei]:\n",
    "                meet_the_most_left = True\n",
    "                next_root = i\n",
    "            # 进入最左侧子树后，判断右子树是否比根节点大，否则为False\n",
    "            if meet_the_most_left and arr[i] > arr[ei]: return False\n",
    "        # 左右子树递归\n",
    "        return self.func(arr, si, next_root) and self.func(arr, next_root+1, ei-1)  # 向前挪一格\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "         \n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        parent=float(\"inf\")\n",
    "        stack=[]\n",
    "        for i in range(len(postorder)-1, -1, -1):\n",
    "            cur = postorder[i]\n",
    "            while stack and stack[-1]>cur:\n",
    "                parent= stack.pop()\n",
    "\n",
    "            if cur>parent:\n",
    "                return False\n",
    "            \n",
    "            stack.append(cur)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def split(arr):\n",
    "            if not arr:return True\n",
    "            left = []\n",
    "            right = []\n",
    "            i = 0\n",
    "            while arr[i]<arr[-1]:\n",
    "                left.append(arr[i])\n",
    "                i+=1\n",
    "            for k in range(i,len(arr)-1):\n",
    "                if arr[k] > arr[-1]:\n",
    "                    right.append(arr[k])\n",
    "                else:\n",
    "                    return False\n",
    "            return split(left) and split(right)\n",
    "        return split(postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "\n",
    "        def recur(left, right):\n",
    "            if left >= right:\n",
    "                return True\n",
    "            i = left\n",
    "            while postorder[i] < postorder[right]:\n",
    "                i += 1\n",
    "            right_subtree = i\n",
    "            while postorder[i] > postorder[right]:\n",
    "                i += 1\n",
    "            return i == right and recur(left, right_subtree - 1) and recur(right_subtree, right - 1)\n",
    "\n",
    "        return recur(0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j: return True\n",
    "            p = i\n",
    "            while postorder[p] < postorder[j]: p += 1\n",
    "            m = p\n",
    "            while postorder[p] > postorder[j]: p += 1\n",
    "            return p == j and recur(i, m - 1) and recur(m, j - 1)\n",
    "\n",
    "        return recur(0, len(postorder) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            for m in range(j+1):\n",
    "                if postorder[m] > postorder[j]:\n",
    "                    break\n",
    "            for n in range(m, j+1):\n",
    "                if postorder[n] <= postorder[j]:\n",
    "                    break\n",
    "            return n == j and recur(i, m-1) and recur(m, j-1)\n",
    "        \n",
    "        return recur(0, len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "\n",
    "        def rootcheck(seqs):\n",
    "            if seqs is None: \n",
    "                # print('postorder is None')\n",
    "                return False\n",
    "            if len(seqs)<=2:\n",
    "                return True\n",
    "            last = seqs[-1]\n",
    "            i = len(seqs)-1\n",
    "            # flag = True\n",
    "            while i>=0:\n",
    "                if seqs[i] <last:\n",
    "                    break\n",
    "                i -= 1\n",
    "            # print(i,seqs)\n",
    "            if i<0 or i == len(seqs)-1:\n",
    "                return rootcheck(seqs[:-1])\n",
    "\n",
    "            else:\n",
    "                if len(list(filter(lambda x: x >= last, seqs[:i])))>0:\n",
    "                    # print(list(filter(lambda x: x >= last, seqs[:i])))\n",
    "                    return False\n",
    "                return rootcheck(seqs[:i+1]) and rootcheck(seqs[i+1:-1])\n",
    "                # print(seqs[i])\n",
    "\n",
    "        # if postorder is None:\n",
    "        #     return False\n",
    "\n",
    "        return rootcheck(postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def verify(i,j):\n",
    "            if i >= j: return True\n",
    "            index = i\n",
    "            while postorder[index] < postorder[j] : index += 1\n",
    "            right = index\n",
    "            while postorder[index] > postorder[j] : index += 1\n",
    "            return index == j and verify(i, right-1) and verify(right, j-1)\n",
    "        return verify(0, len(postorder)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "\n",
    "        def recur(left, right):\n",
    "            if left > right:\n",
    "                return True\n",
    "            i = left\n",
    "            while postorder[i] < postorder[right]:\n",
    "                i += 1\n",
    "            right_subtree = i\n",
    "            while postorder[i] > postorder[right]:\n",
    "                i += 1\n",
    "            return i == right and recur(left, right_subtree - 1) and recur(right_subtree, right - 1)\n",
    "\n",
    "        return recur(0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def check(i, j):\n",
    "            if i>=j:\n",
    "                return True\n",
    "            print(f'DEBUG list {postorder[i:j+1]}')\n",
    "            ridx = -1\n",
    "            for x in range(i, j):\n",
    "                if ridx==-1 and  postorder[x] > postorder[j]:\n",
    "                    ridx = x\n",
    "                elif ridx!=-1 and postorder[x] < postorder[j]:\n",
    "                    return False\n",
    "            print(f'DEBUG ridx={ridx}')\n",
    "            if ridx == -1:\n",
    "                return check(i, j-1)\n",
    "            return check(i, ridx-1) and check(ridx, j-1)\n",
    "        return check(0, len(postorder)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        stack,root=[],float(\"inf\")\n",
    "        for i in range(len(postorder)-1,-1,-1):\n",
    "            if postorder[i]>root:return False\n",
    "            while stack and postorder[i]<stack[-1]:\n",
    "                root = stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recur(self, postorder, left, right):\n",
    "        if left >= right:\n",
    "            return True\n",
    "        m = left\n",
    "        while m < right and postorder[m] < postorder[right]:\n",
    "            m += 1\n",
    "        ret_left = self.recur(postorder, left, m-1) \n",
    "        i = m\n",
    "        while i < right and postorder[i] > postorder[right]:\n",
    "            i += 1\n",
    "        if i != right:\n",
    "            return False\n",
    "        ret_right = self.recur(postorder, m, right-1)\n",
    "        return ret_left and ret_right\n",
    "\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        return self.recur(postorder, 0, len(postorder)-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "\n",
    "        def helper(left, right):\n",
    "            if left >= right:\n",
    "                return True\n",
    "            root_val = postorder[right]\n",
    "            p = left\n",
    "            while postorder[p] < root_val:\n",
    "                p += 1\n",
    "            m = p\n",
    "            while postorder[p] > root_val:\n",
    "                p += 1\n",
    "            return p == right and helper(left, m - 1) and helper(m, right - 1)\n",
    "\n",
    "        return helper(0, len(postorder) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        n = len(postorder)\n",
    "        if n <= 1:\n",
    "            return True\n",
    "        check = postorder[-1]\n",
    "        i = 0\n",
    "        for i in range(n-1):\n",
    "            if postorder[i] < check:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        for j in range(i, n-1):\n",
    "            if postorder[j] < check:\n",
    "                return False\n",
    "        return self.verifyTreeOrder(postorder[:i]) and self.verifyTreeOrder(postorder[i:-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def check(i, j):\n",
    "            if i>=j:\n",
    "                return True\n",
    "            # print(f'DEBUG list {postorder[i:j+1]}')\n",
    "            ridx = -1\n",
    "            for x in range(i, j):\n",
    "                if ridx==-1 and  postorder[x] > postorder[j]:\n",
    "                    ridx = x\n",
    "                elif ridx!=-1 and postorder[x] < postorder[j]:\n",
    "                    return False\n",
    "            # print(f'DEBUG ridx={ridx}')\n",
    "            if ridx == -1:\n",
    "                return check(i, j-1)\n",
    "            return check(i, ridx-1) and check(ridx, j-1)\n",
    "        return check(0, len(postorder)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def check(pre: List[int]):\n",
    "            if not pre:\n",
    "                return True\n",
    "            if len(pre) == 1:\n",
    "                return True\n",
    "\n",
    "            root = pre.pop(0)\n",
    "            index = 0\n",
    "            while index < len(pre) and pre[index] > root:\n",
    "                index += 1\n",
    "            t = index\n",
    "            while t < len(pre):\n",
    "                if pre[t] > root:\n",
    "                    return False\n",
    "                t += 1\n",
    "            r = pre[0:index]\n",
    "            l = pre[index:]\n",
    "            # print(l,r,root)\n",
    "            return check(r) and check(l)\n",
    "\n",
    "        pre = postorder[::-1]\n",
    "        # print(pre)\n",
    "        return check(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if not postorder:\n",
    "            return True\n",
    "        n = len(postorder)\n",
    "        root = postorder[-1]\n",
    "        for i in range(n):\n",
    "            if postorder[i] > root:\n",
    "                break\n",
    "        left = postorder[:i]\n",
    "        right = postorder[i:n-1]\n",
    "        if right and min(right) < root:\n",
    "            return False\n",
    "        flag1 = self.verifyTreeOrder(left)\n",
    "        flag2 = self.verifyTreeOrder(right)\n",
    "        return flag1 and flag2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return True\n",
    "            root_val = postorder[right]\n",
    "            p = left\n",
    "            while postorder[p] < root_val:\n",
    "                p += 1\n",
    "            mid = p\n",
    "            while postorder[p] > root_val:\n",
    "                p += 1\n",
    "            return p == right and helper(left, mid - 1) and helper(mid, right - 1)\n",
    "\n",
    "        return helper(0, len(postorder) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        return self.func(postorder, 0, len(postorder)-1)\n",
    "\n",
    "    # # 后序遍历：左、右、中\n",
    "    # def func(self, arr, si, ei):\n",
    "    #     # 若当前子树为空则返回True\n",
    "    #     if si >= ei: return True\n",
    "    #     meet_the_most_left = False\n",
    "    #     next_root = si\n",
    "    #     for i in range(ei-1, si-1, -1):\n",
    "    #         # 先扫描最左侧的左子树\n",
    "    #         if not meet_the_most_left and arr[i] < arr[ei]:\n",
    "    #             meet_the_most_left = True\n",
    "    #             next_root = i\n",
    "    #         # 进入最左侧子树后，判断右子树是否比根节点大，否则为False\n",
    "    #         if meet_the_most_left and arr[i] > arr[ei]: return False\n",
    "    #     # 左右子树递归\n",
    "    #     return self.func(arr, si, next_root) and self.func(arr, next_root+1, ei-1)  # 向前挪一格\n",
    "\n",
    "    def func(self, arr, si, ei):\n",
    "        # 若当前子树为空则返回True\n",
    "        if si >= ei: return True\n",
    "        split_index = si\n",
    "        trun = False\n",
    "        \n",
    "        for i in range(si, ei + 1):\n",
    "            # 在从左向右遍历的过程中，首先需要找到左右子树的分界点：第一个大于根节点的节点必定是右子树的最左侧叶子\n",
    "            if not trun and arr[i] > arr[ei]:\n",
    "                split_index = i\n",
    "                trun = True\n",
    "            \n",
    "            # 当找到左右子树分界点后，再向右遍历，这时如果发现存在比目前根节点还要小的节点，就说明右子树不合法\n",
    "            if trun and arr[i] < arr[ei]:\n",
    "                return False\n",
    "            \n",
    "        # 进一步判断左右两棵子树的情况\n",
    "        # ei - 1用于跳开当前根节点\n",
    "        return self.func(arr, si, split_index) and self.func(arr, split_index, ei - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque            \n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        parent=float(\"inf\")\n",
    "        stack=deque([])\n",
    "        for i in range(len(postorder)-1, -1, -1):\n",
    "            cur = postorder[i]\n",
    "            while len(stack)>0 and stack[-1]>cur:\n",
    "                parent= stack.pop()\n",
    "\n",
    "            if cur>parent:\n",
    "                return False\n",
    "            \n",
    "            stack.append(cur)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i,j):\n",
    "            if i>=j:return True\n",
    "            p = i\n",
    "            while postorder[p]<postorder[j]:p+=1\n",
    "            m = p\n",
    "            while postorder[p]>postorder[j]:p+=1\n",
    "            return p==j and recur(i,m-1) and recur(m,j-1)\n",
    "        \n",
    "        return recur(0,len(postorder)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i>=j: return True\n",
    "            p = i\n",
    "            while postorder[p]<postorder[j]: p+=1\n",
    "            m = p\n",
    "            while postorder[p]>postorder[j]: p+=1\n",
    "            return p == j and recur(i, m-1) and recur(m, j-1)\n",
    "        return recur(0, len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder):\n",
    "        length = len(postorder)\n",
    "        def rec(left, right):\n",
    "            if left >= right:\n",
    "                return True\n",
    "            cur = left\n",
    "            while cur <= right and postorder[cur] < postorder[right]:\n",
    "                cur += 1\n",
    "            left_tree_root = cur - 1\n",
    "            while cur <= right and postorder[cur] > postorder[right]:\n",
    "                cur += 1\n",
    "            return cur == right and rec(left, left_tree_root) and rec(left_tree_root+1, right-1)\n",
    "        return not postorder or rec(0, length-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        stack, root = [], float(\"+inf\")\n",
    "        for i in range(len(postorder) - 1, -1, -1):\n",
    "            if postorder[i] > root: return False\n",
    "            while(stack and postorder[i] < stack[-1]):\n",
    "                root = stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        if len(postorder)<=1:\n",
    "            return True\n",
    "        else:\n",
    "            i=2\n",
    "            while i<=len(postorder) and postorder[-i]>postorder[-1]:\n",
    "                i+=1\n",
    "            for j in range(i,len(postorder)+1):\n",
    "                if postorder[-j]>postorder[-1]:\n",
    "                    return False\n",
    "            return self.verifyTreeOrder(postorder[:-i+1]) and self.verifyTreeOrder(postorder[-i+1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque            \n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        parent=float(\"inf\")\n",
    "        stack=[]\n",
    "        for i in range(len(postorder)-1, -1, -1):\n",
    "            cur = postorder[i]\n",
    "            while len(stack)>0 and stack[-1]>cur:\n",
    "                parent= stack.pop()\n",
    "\n",
    "            if cur>parent:\n",
    "                return False\n",
    "            \n",
    "            stack.append(cur)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j: return True\n",
    "            p = i\n",
    "            while postorder[p] < postorder[j]: p += 1\n",
    "            m = p\n",
    "            while postorder[p] > postorder[j]: p += 1\n",
    "            return p == j and recur(i, m - 1) and recur(m, j - 1)\n",
    "\n",
    "        return recur(0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "#         if not postorder:\n",
    "#             return True\n",
    "#         root = postorder[-1]\n",
    "#         left = []\n",
    "#         right = []\n",
    "#         flag1 = True\n",
    "#         flag2 = True\n",
    "#         for i in range(len(postorder)):\n",
    "#             if postorder[i] > root:\n",
    "#                 left = postorder[:i]\n",
    "#                 right = postorder[i:-1]\n",
    "#                 break\n",
    "#         if right and min(right) < root:\n",
    "#             return False\n",
    "#         if left:\n",
    "#             flag1 = self.verifyTreeOrder(left)\n",
    "#         if right:\n",
    "#             flag2 = self.verifyTreeOrder(right)\n",
    "#         return flag1 and flag2\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        #二叉搜索树的性质：\n",
    "        #如果左子树不空，左子树的所有节点的值小于根节点的值。\n",
    "        #如果右子树不空，则右子树所有节点的值大于跟节点的值。\n",
    "        if postorder == []:return True\n",
    "        n = len(postorder)\n",
    "        for i in range(n):\n",
    "            if postorder[i] > postorder[-1]:\n",
    "                break\n",
    "        left_tree = postorder[:i]\n",
    "        right_tree = postorder[i:n-1]\n",
    "        print(postorder,left_tree,right_tree)\n",
    "        for num in right_tree:\n",
    "            if num < postorder[-1]:\n",
    "                return False\n",
    "        return self.verifyTreeOrder(left_tree) and self.verifyTreeOrder(right_tree)   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        # 用递归的思路来考虑\n",
    "        def check(nums):\n",
    "            if len(nums) <= 2:\n",
    "                return True \n",
    "            else:\n",
    "                root = nums[-1]\n",
    "                leftindex = 0 \n",
    "                for i in range(len(nums)-1):\n",
    "                    if nums[i] < nums[-1]:\n",
    "                        leftindex = i \n",
    "                    else:\n",
    "                        break \n",
    "                for i in range(leftindex+1,len(nums)-1):\n",
    "                    if nums[i] < nums[-1]:\n",
    "                        return False \n",
    "                return check(nums[:leftindex+1]) and check(nums[leftindex+1:len(nums)-1])\n",
    "        return check(postorder)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i,j):\n",
    "            if i>=j:\n",
    "                return True\n",
    "            p=i\n",
    "            while postorder[p]<postorder[j]:\n",
    "                p+=1\n",
    "            m=p\n",
    "            while postorder[p]>postorder[j]:\n",
    "                p+=1\n",
    "            return p==j and recur(i,m-1) and recur(m,j-1)\n",
    "\n",
    "        return recur(0,len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        # 后序遍历：左右根\n",
    "        stack=[]\n",
    "        root=float(\"inf\")\n",
    "        # 后序遍历倒序：根右（根右是单调递增的）左\n",
    "        for i in range(len(postorder)-1,-1,-1):\n",
    "            if postorder[i]>root:\n",
    "                return False\n",
    "            # 单调递增栈\n",
    "            while stack and postorder[i]<stack[-1]:\n",
    "                root=stack.pop()\n",
    "            stack.append(postorder[i])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i, j):\n",
    "            if i >= j: return True\n",
    "            p = i\n",
    "            while postorder[p] < postorder[j]: \n",
    "                p += 1\n",
    "            m = p\n",
    "            while postorder[p] > postorder[j]:\n",
    "                p += 1\n",
    "            return p == j and recur(i, m-1) and recur(m, j-1)\n",
    "        return recur(0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def recur(i,j):\n",
    "            if i>=j:\n",
    "                return True\n",
    "            p=i\n",
    "            while postorder[p]<postorder[j]:\n",
    "                p+=1\n",
    "            m=p\n",
    "            while postorder[p]>postorder[j]:\n",
    "                p+=1\n",
    "            return p==j and recur(i,m-1) and recur(m,j-1)\n",
    "\n",
    "        return recur(0,len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return True\n",
    "            head = left\n",
    "            while postorder[head] < postorder[right]:\n",
    "                head += 1\n",
    "            mid = head\n",
    "            while postorder[head] > postorder[right]:\n",
    "                head += 1\n",
    "            return head == right and helper(left, mid-1) and helper(mid, right-1)\n",
    "\n",
    "        return helper(0, len(postorder)-1)\n",
    "    \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        def verify(subsequence):\n",
    "            if len(subsequence) <= 1:\n",
    "                return True\n",
    "            root = subsequence[-1]\n",
    "            # Find the first element greater than root, which marks the start of the right subtree\n",
    "            for i in range(len(subsequence)):\n",
    "                if subsequence[i] > root:\n",
    "                    break\n",
    "            # Verify that all elements in the right subtree are greater than root\n",
    "            for j in range(i, len(subsequence) - 1):\n",
    "                if subsequence[j] < root:\n",
    "                    return False\n",
    "            # Recursively verify the left and right subtrees\n",
    "            return verify(subsequence[:i]) and verify(subsequence[i:-1])\n",
    "        \n",
    "        return verify(postorder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verifyTreeOrder(self, postorder: List[int]) -> bool:\n",
    "        self.ans=True\n",
    "        def partition(nums,l,r):\n",
    "            val = postorder[r]\n",
    "            # lo,hi=l,r-1\n",
    "            # while lo<=hi:\n",
    "            #     mid=lo+(hi-lo)//2\n",
    "            #     if nums[mid]<val:\n",
    "            #         lo=mid+1\n",
    "            #     else:\n",
    "            #         hi=mid-1\n",
    "\n",
    "            # #[l,lo)<val [lo,r]>val\n",
    "            \n",
    "            i=r\n",
    "            for j in range(l,r):\n",
    "                if nums[j]>val:\n",
    "                    i=j\n",
    "                    break\n",
    "            if i==r:\n",
    "                return r\n",
    "            while i<r:\n",
    "                \n",
    "                if nums[i]<val:\n",
    "                    return -1\n",
    "                i+=1\n",
    "                    \n",
    "            return j\n",
    "            #return i [l,i-1] [i,r-1] or -1 不能切割\n",
    "\n",
    "\n",
    "        def dfs(postorder,l,r):\n",
    "            if r-l<=1 or not self.ans:\n",
    "                return \n",
    "            \n",
    "            i=partition(postorder,l,r)\n",
    "            if i==-1:\n",
    "                self.ans=False\n",
    "                return \n",
    "            else:\n",
    "                dfs(postorder,l,i-1)\n",
    "                dfs(postorder,i,r-1)\n",
    "                return \n",
    "            \n",
    "        dfs(postorder, 0, len(postorder)-1)\n",
    "        return self.ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
